#
# @lc app=leetcode.cn id=38 lang=python
#
# [38] 外观数列
#

# @lc code=start
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return "1"
        pre_result = self.countAndSay(n-1)

        length = len(pre_result)
        start = 0
        result = ''

        for i in range(1, length+1):
            if i == length:
                result += str(i-start) + pre_result[start]
            elif pre_result[i] != pre_result[start]:
                result += str(i-start) + pre_result[start]
                start = i

        return result

        

# @lc code=end


if __name__ == "__main__":
    solution = Solution()
    n = 5
    result_string = solution.countAndSay(n=n)
    print(f'{n}:{result_string}')